#pragma GCC optimize("Ofast", "unroll-loops")
#include<bits/stdc++.h>
using namespace std; using ll = long long;
#define For(i, j, k) for ( int i = (j) ; i <= (k) ; i++ )
#define Fol(i, j, k) for ( int i = (j) ; i >= (k) ; i-- )
constexpr ll inf = numeric_limits < ll >::max() >> 1;
int n, m, q, a[150009], l, r, pos[150009], len; ll mn, b[150009], ans;
int main()
{
	freopen("clear.in", "r", stdin), freopen("clear.out", "w", stdout);
	cin.tie(nullptr) -> sync_with_stdio(false);
	cin >> n >> m >> q;
	For(i, 1, n) cin >> a[i];
	For(_, 1, q)
	{
		cin >> l >> r, b[l] = a[l], b[r + 1] = -inf, len = ans = 0;
		For(i, l + 1, r) b[i] = a[i] - a[i - 1];
		Fol(i, r + 1, l + 1) if ( b[i] < 0 ) pos[++len] = i;
		For(i, l, r) for ( ans += max(0ll, b[i]) ; b[i] > 0 ; )
			if ( pos[len] > i + m ) b[i + m] += b[i], b[i] = 0;
			else mn = min(b[i], -b[pos[len]]), b[i] -= mn, ( b[pos[len]] += mn ) || len--;
		cout << ans << '\n';
	}
	return 0;
}